package number_76;

import java.util.*;

public class Solution {
    public String minWindow1(String s, String t) {
        Set<Character> set = new HashSet<>();
        for (char c : t.toCharArray()) {
            set.add(c);
        }
        int start = 0, end = set.size();
        int sLen = Integer.MAX_VALUE;
        String res = "";

        while (end <= s.length()) {
            String tmp = s.substring(start, end);
            if (isContain(tmp, set)) {
                if (tmp.length() < sLen) {
                    sLen = tmp.length();
                    res = tmp;
                }
                start++;
                while (end - start >= set.size()) {
                    String tmp2 = s.substring(start, end);
                    if (isContain(tmp2, set)) {
                        if (tmp2.length() < sLen) {
                            sLen = tmp2.length();
                            res = tmp2;
                        }
                    } else {
                        break;
                    }
                    start++;
                }
            }
            end++;
        }
        return res;
    }

    private boolean isContain(String string, Set<Character> set) {
        Set<Character> set1 = new HashSet<>(set);
        int number = set.size();
        for (char c : string.toCharArray()) {
            if (set1.contains(c)) {
                number--;
                set1.remove(c);
            }
        }
        return number == 0;
    }
    Map<Character, Integer> oriMap = new HashMap<>();
    Map<Character, Integer> cntMap = new HashMap<>();
    public String minWindow(String s, String t) {
        for (char c : t.toCharArray()) {
            oriMap.put(c, oriMap.getOrDefault(c, 0) + 1);
        }
        int left = 0, right = -1;
        int len = Integer.MAX_VALUE, ansLeft = -1, ansRight = -1;
        int sLen = s.length();

        while (right < sLen) {
            ++right;
            if (right < sLen && oriMap.containsKey(s.charAt(right))) {
                cntMap.put(s.charAt(right), cntMap.getOrDefault(s.charAt(right), 0) + 1);
            }
            while (check() && left <= right) {
                if (right - left + 1 < len) {
                    len = right - left + 1;
                    ansLeft = left;
                    ansRight = right + 1;
                }
                if (oriMap.containsKey(s.charAt(left))) {
                    cntMap.put(s.charAt(left), cntMap.getOrDefault(s.charAt(left), 0) - 1);
                }
                ++left;
            }
        }
        return ansLeft == -1 ? "" : s.substring(ansLeft, ansRight);

    }

    private boolean check() {
        Iterator iter = oriMap.entrySet().iterator();
        while (iter.hasNext()) {
            Map.Entry entry = (Map.Entry) iter.next();
            Character key = (Character) entry.getKey();
            Integer value = (Integer) entry.getValue();
            if (cntMap.getOrDefault(key, 0) < value) {
                return false;
            }

        }
        return true;
    }

    public static void main(String[] args) {
        new Solution().minWindow("ADOBECODEBANC", "ABC");
    }
}
